This invention relates, in general, to microprocessing units, and more specifically, to a microprocessor for logic programming, functional programming, and symbolic computing.
Conventional microprocessor architectures are divided into two categories, CISC (complex instruction set computer) architectures and RISC (reduced instruction set architectures). All sequential and parallel computers are composed of either single processors or multiple-element groups of processing elements (parallel processors) that are based on CISC, RISC or both types of computer architecture. Giving an example for each class of computer: a sequential computer with a CISC architecture is the Motorola 68040; a sequential computer with a RISC architecture is the Motorola 88000; a parallel computer with a CISC architecture is the NASA Jet Propulsion Laboratory Hypercube with Motorola 68020 processing elements; a parallel computer with a RISC architecture is the Bolt, Beranek and Newman (BBN) Butterfly II with Motorola 88000 processing elements.
None of the above computers are ideally suited to execute logic programs, functional programs and symbolic programs written in languages exemplified by but not limited to Prolog, Scheme, and ML. The reasons why these computers specifically, and all microprocessors in general, are unsuitable are listed with accompanying discussions in the following paragraphs numbered (1), (2), (3), (4) and (5).
(1) These architectures do not have support for tagged data types. Tagged data types are dealt with by assigning an arbitrary bit field with the meaning of the tag (which distinguishes one kind of datum from another). However, the bit field is not treated independently by the architecture, but is part of a single value which is a number. Conventional microprocessors distinguish tagged data types by correspondences within ranges of representable numbers. (2) The operations necessary to execute logic, functional, and symbolic programming differ in type and frequency from those operations supported by conventional architectures. Conventional microprocessors require multiple instructions to extract bit fields from a number, compare bit fields independently to determine membership in a class of tagged data types, and construct tagged data objects.
(3) Logic, functional, and symbolic programs use irregular data structures such as heaps and stacks which are composed of aggregate items containing data of dissimilar size. Zero or single cycle index and bounds checks are required to establish that a single datum is a member of a given aggregate. Conventional microprocessors require multiple instructions to perform these checks.
(4) Logic, functional, and symbolic programs execute short branches frequently based on the type of a data object being processed. Conventional microprocessors control execution of short code fragments as a stream of non-contiguous instruction sequences linked by conditional branch instructions. Due to the resulting high branch frequency pipelined execution and interleaved memory, addressing is not effective in a conventional microprocessor.
(5) Logic, functional and symbolic programs further are not characterized by long, frequent, and shallow series of procedure calls, as are programs written in procedural languages such as Pascal, C and Ada. Instead, logic, functional and symbolic programs have long and deep sequences of linked procedure calls in which there are many generations of call, and in which the most recent generation typically does not return to its parent caller but to its eldest ancestor. Register windows, such as are found in conventional microprocessors, are efficient and effective for parent-child sequences of procedure calls, but not for generational procedure calling.
A LOW RISC microprocessor evolved from a Warren Abstract Prolog Machine (WAM) as the underlying functions of the WAM were identified, and then organized as a simple abstract machine (SAM). The set of primitive operations comprising the SAM instruction set was then reduced yielding the present invention known as the LOW RISC III, for three reasons:
1. Globally optimized code is generated in terms of the primitives, omitting superfluous operations executed by the more general WAM and SAM instructions.
2. Single instructions are provided for critical operations, such as a multi-way dispatch based on the value of a tag. In addition, tag and value processing are performed in parallel. Note that neither of these functions is provided in RISC processors such as the MIPS machine, the Berkeley RISC I and the Berkeley RISC II.
3. The implementation would pipeline execution of the primitives, thus reducing the primitives' apparent execution time.